{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Kth Smallest Element in a BST"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-search-tree #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉搜索树 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: kthSmallest"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉搜索树中第K小的元素"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个二叉搜索树的根节点 <code>root</code> ，和一个整数 <code>k</code> ，请你设计一个算法查找其中第 <code>k</code><strong> </strong>个最小元素（从 1 开始计数）。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/01/28/kthtree1.jpg\" style=\"width: 212px; height: 301px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [3,1,4,null,2], k = 1\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/01/28/kthtree2.jpg\" style=\"width: 382px; height: 302px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [5,3,6,2,4,null,null,1], k = 3\n",
    "<strong>输出：</strong>3\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中的节点数为 <code>n</code> 。</li>\n",
    "\t<li><code>1 <= k <= n <= 10<sup>4</sup></code></li>\n",
    "\t<li><code>0 <= Node.val <= 10<sup>4</sup></code></li>\n",
    "</ul>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>进阶：</strong>如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 <code>k</code> 小的值，你将如何优化算法？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [kth-smallest-element-in-a-bst](https://leetcode.cn/problems/kth-smallest-element-in-a-bst/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [kth-smallest-element-in-a-bst](https://leetcode.cn/problems/kth-smallest-element-in-a-bst/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,1,4,null,2]\\n1', '[5,3,6,2,4,null,null,1]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        # curr = 0\n",
    "        # kth_smallest = -1\n",
    "\n",
    "        # def inorder(node):\n",
    "        #     nonlocal curr\n",
    "        #     nonlocal kth_smallest\n",
    "        #     if node is None:\n",
    "        #         return\n",
    "        #     inorder(node.left)\n",
    "        #     curr += 1\n",
    "        #     if curr == k:\n",
    "        #         kth_smallest = node.val\n",
    "        #         return\n",
    "        #     inorder(node.right)\n",
    "        # inorder(root)\n",
    "        # return kth_smallest\n",
    "\n",
    "        # def inorder(root):\n",
    "        #     return inorder(root.left) +[root.val] + inorder(root.right) if root else []\n",
    "        # return inorder(root)[k-1]\n",
    "\n",
    "        stack = list()\n",
    "\n",
    "        while True:\n",
    "            while root:\n",
    "                stack.append(root)\n",
    "                root = root.left\n",
    "            root = stack.pop()\n",
    "            k -= 1\n",
    "            if not k:\n",
    "                return root.val\n",
    "            else:\n",
    "                root = root.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallest(self, root, k):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type k: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if root == None:\n",
    "            return\n",
    "        nodes = []\n",
    "        if root.right!=None:\n",
    "            nodes.append(root.right)\n",
    "            root.right = None\n",
    "        nodes.append(root)\n",
    "        if root.left!=None:\n",
    "            nodes.append(root.left)\n",
    "            root.left = None\n",
    "        count = 0\n",
    "        while nodes!=[]:\n",
    "            node = nodes[-1]\n",
    "            nodes = nodes[:len(nodes)-1]\n",
    "            if node.right == None and node.left == None:\n",
    "                count+=1\n",
    "                if count == k:\n",
    "                    return node.val\n",
    "            else:\n",
    "                if node.right!=None:\n",
    "                    nodes.append(node.right)\n",
    "                    node.right = None\n",
    "                nodes.append(node)\n",
    "                if node.left!=None:\n",
    "                    nodes.append(node.left)\n",
    "                    node.left = None\n",
    "            \n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallest(self, root, k):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type k: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        def dfs(node, cur):\n",
    "            if not node:\n",
    "                return cur, None\n",
    "            cur, res = dfs(node.left, cur)\n",
    "            if cur == k:\n",
    "                return cur, res\n",
    "            cur += 1\n",
    "            if cur == k:\n",
    "                return cur, node\n",
    "            return dfs(node.right, cur)\n",
    "        return dfs(root, 0)[1].val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallest(self, root: 'TreeNode', k: 'int') -> 'int':\n",
    "        l = []\n",
    "        l.append(root)\n",
    "        res = []\n",
    "        while len(l):\n",
    "            t = l.pop()\n",
    "            res.append(t.val)\n",
    "            if t.left: l.append(t.left)\n",
    "            if t.right: l.append(t.right)\n",
    "        res = sorted(res)\n",
    "        return res[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def rootPath(self,root,k,res):\n",
    "        if root is None:\n",
    "            return None \n",
    "        \n",
    "        self.rootPath(root.left,k,res) \n",
    "        k[0] -=1 \n",
    "        if k[0] == 0:\n",
    "            res[0] = root.val\n",
    "        \n",
    "        self.rootPath(root.right,k,res)\n",
    "    \n",
    "    def kthSmallest(self, root, k):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type k: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        res = [-1]\n",
    "        self.rootPath(root,[k],res)\n",
    "        return res[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallest(self, root, k):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type k: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        q = [root]\n",
    "        res = set()\n",
    "        while q:\n",
    "            cur = q.pop(0)\n",
    "            res.add(cur.val)\n",
    "            if cur.left is not None:\n",
    "                q.append(cur.left)\n",
    "            if cur.right is not None:\n",
    "                q.append(cur.right)\n",
    "        return sorted(res)[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def kthSmallest(self, root: TreeNode, k: int) -> int:\n",
    "        ret = self.inorder(root)\n",
    "        return ret[k-1]\n",
    "        \n",
    "    def inorder(self, root: TreeNode) -> list():\n",
    "        ret = list()\n",
    "        if root is None:\n",
    "            return ret\n",
    "        ret += self.inorder(root.left)\n",
    "        ret.append(root.val)\n",
    "        ret += self.inorder(root.right)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def fun(self, root, ls):\n",
    "        if root:\n",
    "            new=TreeNode(root.val)\n",
    "            ls.append(new)\n",
    "            self.fun(root.left, ls)\n",
    "            self.fun(root.right, ls)\n",
    "\n",
    "    def kthSmallest(self, root, k):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type k: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        def compTreeNode(elem):\n",
    "            return elem.val\n",
    "        ret=[]\n",
    "        self.fun(root,ret)\n",
    "        ret.sort(key=compTreeNode)\n",
    "        return ret[k-1].val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallest(self, root: TreeNode, k: int) -> int:\n",
    "        ans, stack = [], [root]\n",
    "        while stack != []:\n",
    "            node = stack[-1]\n",
    "            if node.left:\n",
    "                stack.append(node.left)\n",
    "                node.left = None\n",
    "            else:\n",
    "                ans.append(node.val)\n",
    "                node = stack.pop()\n",
    "                if node.right:\n",
    "                    stack.append(node.right)\n",
    "        return ans[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallest(self, root: TreeNode, k: int) -> int:\n",
    "        #中序遍历\n",
    "        queue = [root]\n",
    "        res = []\n",
    "        \n",
    "        while(len(queue) > 0):\n",
    "            node = queue.pop()\n",
    "\n",
    "            if not node.left and not node.right:\n",
    "                res.append(node.val)\n",
    "                if (len(res) == k):\n",
    "                    return res[k-1]\n",
    "            else:\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "                    node.right = None\n",
    "                queue.append(node)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                    node.left = None\n",
    "                \n",
    "                \n",
    "        return res[k-1]\n",
    "            \n",
    "            \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallest(self, root: TreeNode, k: int) -> int:\n",
    "        res=[]\n",
    "        def hel(root):\n",
    "            if not root or len(res)==k:\n",
    "                return res\n",
    "            root.left=hel(root.left)\n",
    "            res.append(root.val)\n",
    "            root.right=hel(root.right)\n",
    "        hel(root)\n",
    "        return res[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from itertools import islice\n",
    "\n",
    "def inorder_iterator(root):\n",
    "    stack = [root] if root else []\n",
    "    while stack:\n",
    "        node = stack.pop()\n",
    "        if node.right:\n",
    "            stack.append(node.right)\n",
    "            node.right = None\n",
    "        if node.left:\n",
    "            stack.append(node)\n",
    "            stack.append(node.left)\n",
    "            node.left = None\n",
    "        else:\n",
    "            yield node.val\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallest(self, root: TreeNode, k: int) -> int:\n",
    "        return next(islice(inorder_iterator(root), k-1, k))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "def inorder_iterator(root):\n",
    "    stack = [root] if root else []\n",
    "    while stack:\n",
    "        node = stack.pop()\n",
    "        if node.right:\n",
    "            stack.append(node.right)\n",
    "            node.right = None\n",
    "        if node.left:\n",
    "            stack.append(node)\n",
    "            stack.append(node.left)\n",
    "            node.left = None\n",
    "        else:\n",
    "            yield node.val\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallest(self, root: TreeNode, k: int) -> int:\n",
    "        return next(v for i, v in zip(range(k), inorder_iterator(root)) if i == k-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthSmallest(self, root: TreeNode, k: int) -> int:\n",
    "        if not root:    return None\n",
    "        num_ptr = 0\n",
    "        stack = [root]\n",
    "        while stack:\n",
    "            top = stack[-1]\n",
    "            if top.left:\n",
    "                stack.append(top.left)\n",
    "                top.left = None\n",
    "            else:\n",
    "                num_ptr += 1\n",
    "                if num_ptr == k:    return top.val\n",
    "                stack.pop()\n",
    "                if top.right:\n",
    "                    stack.append(top.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallest(self, root: TreeNode, k: int) -> int:\n",
    "        nodes = [root]\n",
    "        # inorder travell\n",
    "        id = 0\n",
    "        \n",
    "        while nodes:\n",
    "            node = nodes.pop()\n",
    "            if not isinstance(node, TreeNode):\n",
    "                id += 1\n",
    "            else:\n",
    "                if node.right:\n",
    "                    nodes.append(node.right)\n",
    "                nodes.append(node.val)\n",
    "                if node.left:\n",
    "                    nodes.append(node.left)\n",
    "            if id == k:\n",
    "                return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallest(self, root: TreeNode, k: int) -> int:\n",
    "        stack = []\n",
    "        \n",
    "        while True:\n",
    "            while root:\n",
    "                stack.append(root)\n",
    "                root = root.left\n",
    "            if len(stack) == 0:\n",
    "                break\n",
    "            root = stack.pop()\n",
    "            k -= 1\n",
    "            if k == 0:\n",
    "                return root.val\n",
    "            root = root.right\n",
    "        \n",
    "        return None\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallest(self, root: TreeNode, k: int) -> int:\n",
    "        def inorder(root):\n",
    "            return inorder(root.left) + [root.val] + inorder(root.right) if root else []\n",
    "        return inorder(root)[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        stack = [root]\n",
    "        node = root\n",
    "        res = []\n",
    "        while stack:\n",
    "            while node.left:\n",
    "                stack.append(node.left)\n",
    "                node = node.left\n",
    "            node = stack.pop()\n",
    "            res.append(node.val)\n",
    "            node.left = None\n",
    "            if node.right:\n",
    "                stack.append(node.right)\n",
    "                node = node.right\n",
    "\n",
    "\n",
    "        return res[k-1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        stack = [root]\n",
    "        count = 0\n",
    "        while len(stack) > 0:\n",
    "            cur = stack.pop()\n",
    "            if cur.right is None and cur.left is None:\n",
    "                count += 1\n",
    "                if count == k:\n",
    "                    return cur.val\n",
    "                continue\n",
    "            if cur.right:\n",
    "                stack.append(cur.right)\n",
    "                cur.right = None\n",
    "            stack.append(cur)\n",
    "            if cur.left:\n",
    "                stack.append(cur.left)\n",
    "                cur.left = None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        q = [root]\n",
    "        while k > 0:\n",
    "            node = q[-1]\n",
    "            if node.left:\n",
    "                q.append(node.left)\n",
    "                node.left = None\n",
    "            else:\n",
    "                k -= 1\n",
    "                if k == 0 :\n",
    "                    return node.val\n",
    "                else:\n",
    "                    q.pop(-1)\n",
    "                    if node.right:\n",
    "                        q.append(node.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        now = root \n",
    "        stack = deque()\n",
    "        stack.append(now)\n",
    "        tag = 0\n",
    "\n",
    "        while stack:\n",
    "            now = stack.pop()\n",
    "            if not now.left and not now.right:\n",
    "                tag += 1\n",
    "                if tag == k:\n",
    "                    return now.val\n",
    "            else:\n",
    "                right = now.right\n",
    "                left = now.left \n",
    "                now.right = None\n",
    "                now.left = None\n",
    "                if right:\n",
    "                    stack.append(right)\n",
    "                stack.append(now)\n",
    "                if left:\n",
    "                    stack.append(left)\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthSmallest(self, root: TreeNode, k: int) -> int:\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def number(root)->int:\n",
    "            '''\n",
    "            return element number of tree\n",
    "            '''\n",
    "            if root==None:\n",
    "                return 0 \n",
    "            return 1+number(root.left)+number(root.right)\n",
    "\n",
    "        def getk(root,k) -> int:\n",
    "            '''\n",
    "            return k-th smallest element  of tree\n",
    "            '''  \n",
    "            if k<=number(root.left):\n",
    "                return getk(root.left,k)\n",
    "            elif k==1+number(root.left):\n",
    "                # 递归边界 \n",
    "                return root.val \n",
    "            return getk(root.right,k-1-number(root.left))\n",
    "        return getk(root,k)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    \n",
    "    def kthSmallest(self, root: TreeNode, k: int) -> int:\n",
    "        self.k = k\n",
    "        if not root or k == 0:\n",
    "            return None\n",
    "        return self.kthSmallestAux(root, k).val\n",
    "\n",
    "    def kthSmallestAux(self, root: TreeNode, k: int):\n",
    "        target = TreeNode(None)\n",
    "        if root.left:\n",
    "            target = self.kthSmallestAux(root.left, self.k)\n",
    "        if target.val is None:\n",
    "            if self.k == 1:\n",
    "                target = root\n",
    "            self.k -= 1\n",
    "        \n",
    "        if target.val is None and root.right:\n",
    "            target = self.kthSmallestAux(root.right, self.k) \n",
    "        return target\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        stack = []\n",
    "        while root or stack:\n",
    "            while root:\n",
    "                stack.append(root)\n",
    "                root = root.left\n",
    "            root = stack.pop()\n",
    "            k -= 1\n",
    "            if k == 0:\n",
    "                return root.val\n",
    "            root = root.right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        ans,l = [],[]\n",
    "        node = root\n",
    "        while len(ans)<k:\n",
    "            l.append(node)\n",
    "\n",
    "            if node.left != None:\n",
    "                temp = node\n",
    "                node = node.left\n",
    "                temp.left = None\n",
    "            else:\n",
    "                ans.append(node.val)\n",
    "                l.pop()\n",
    "                if node.right != None:\n",
    "                    temp = node\n",
    "                    node = node.right\n",
    "                    temp.right = None\n",
    "                else:\n",
    "                    if l == []:\n",
    "                        break\n",
    "                    node = l.pop()\n",
    "\n",
    "        print(ans)\n",
    "        return ans[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        \n",
    "        dq = deque([root])\n",
    "        while dq:\n",
    "            cur = dq[0]\n",
    "            if cur.left:\n",
    "                dq.appendleft(cur.left)\n",
    "                cur.left = None\n",
    "            else:\n",
    "                if k == 1:\n",
    "                    return cur.val\n",
    "                k -= 1\n",
    "                if cur.right:\n",
    "                    dq[0] = cur.right\n",
    "                else:\n",
    "                    dq.popleft()\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        # 4.27 14.35\n",
    "        self.res = 0\n",
    "        self.count = 0\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "            if self.count > k:\n",
    "                return\n",
    "            dfs(root.left)\n",
    "            self.count+=1\n",
    "            if self.count == k:\n",
    "                self.res = root.val\n",
    "                return\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        self.k = k\n",
    "        self.result = 0\n",
    "        self.mid_order(root)\n",
    "        return self.result\n",
    "\n",
    "    def mid_order(self, node):\n",
    "        if node is None:\n",
    "            return\n",
    "        if self.k == 0:\n",
    "            return\n",
    "        self.mid_order(node.left)\n",
    "        self.k -= 1\n",
    "        if self.k == 0:\n",
    "            self.result = node.val\n",
    "        self.mid_order(node.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthSmallest(self, root: TreeNode, k: int) -> int:\n",
    "        stack = []\n",
    "        while root or stack:\n",
    "            # if root:\n",
    "            #     print(root.val)\n",
    "            while root:\n",
    "                stack.append(root)\n",
    "                root = root.left\n",
    "            root = stack.pop()\n",
    "            print(root.val)\n",
    "            k -= 1\n",
    "            if k == 0:\n",
    "                return root.val\n",
    "            root = root.right\n",
    "        # def f(node):\n",
    "        #     if not node:\n",
    "        #         return \n",
    "        #     f(node.left)\n",
    "        #     ans.append(node.val)\n",
    "        #     f(node.right)\n",
    "        # ans = []\n",
    "        # f(root)\n",
    "        # return ans[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "            dfs(root.left)\n",
    "            if self.k == 0: return \n",
    "            self.k -= 1\n",
    "            if self.k == 0: self.res = root.val\n",
    "            dfs(root.right)\n",
    "        self.k = k\n",
    "        dfs(root)\n",
    "        return self.res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        res = []\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "            dfs(root.left)\n",
    "            res.append(root.val)\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        return res[k-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        def dfs(root):\n",
    "            if not root: return\n",
    "            dfs(root.left)                              # 左\n",
    "            self.k -= 1\n",
    "            if self.k == 0: \n",
    "                self.res = root.val                     # 中\n",
    "                return\n",
    "            dfs(root.right)                             # 右\n",
    "        self.k = k\n",
    "        dfs(root)\n",
    "        return self.res\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
